/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *head = new ListNode;
        ListNode *cur = head;
        int carriage = 0;
        while (l1 || l2 || carriage != 0)
        {
            int x = carriage;
            if (l1)
            {
                x += l1->val;
                l1 = l1->next;
            }
            if (l2)
            {
                x += l2->val;
                l2 = l2->next;
            }
            int val = x % 10;
            carriage = x / 10;

            ListNode *newNode = new ListNode(val);
            cur->next = newNode;
            cur = cur->next;
        }
        return head->next;
    }
};

// 还以为是直接返回int相加的和
class Solution
{
public:
    int add(ListNode *l1, ListNode *l2)
    {
        int x1 = 0, digit = 1;
        int tmp = 0;
        ListNode *cur = l1;
        while (cur)
        {
            tmp += cur->val * digit;
            digit *= 10;
            cur = cur->next;
        }
        int x2 = 0;
        tmp = 0, digit = 0;
        cur = l2;
        while (cur)
        {
            tmp += cur->val * digit;
            digit *= 10;
            cur = cur->next;
        }
        return x1 + x2;
    }
};

class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode *head = new ListNode;
        ListNode *tail = head;
        int carriage = 0;
        ListNode *cur1 = l1, *cur2 = l2;
        while (cur1 || cur2 || carriage)
        {
            if (cur1)
            {
                carriage += cur1->val;
                cur1 = cur1->next;
            }
            if (cur2)
            {
                carriage += cur2->val;
                cur2 = cur2->next;
            }
            tail->next = new ListNode(carriage % 10);
            tail = tail->next;
            carriage /= 10;
        }
        return head->next;
    }
};

// class Solution
// {
// public:
//     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
//     {
//         int carriage = 0;
//         ListNode *ret = new ListNode;
//         ListNode *cur = ret;
//         while (l1 && l2)
//         {
//             int sum = l1->val + l2->val + carriage;
//             carriage = sum / 10;
//             cur->val = sum % 10;
//             if(l1->next || l2->next){
//                 cur->next = new ListNode(carriage);
//             }
//             else{
//                 break;
//             }

//             cur = cur->next;
//             l1 = l1->next;
//             l2 = l2->next;
//         }
//         while (l1)
//         {
//             int sum = l1->val + carriage;
//             carriage = sum / 10;
//             cur->val = sum % 10;
//             cur->next = (l1->next)? new ListNode(carriage) : nullptr;
//             cur = cur->next;
//             l1 = l1->next;
//         }
//         while (l2)
//         {
//             int sum = l2->val + carriage;
//             carriage = sum / 10;
//             cur->val = sum % 10;
//             cur->next = (l2->next)? new ListNode(carriage) : nullptr;
//             cur = cur->next;
//             l2 = l2->next;
//         }
//         return ret;
//     }
// };